#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 头插法来新建链表,新插入的每个元素都要插入前一个元素的前面
// LNode*是结构体指针，跟LinkList是完全等价的
void list_head_insert(LinkList &L)
{
    L=(LNode*)malloc(sizeof(LNode));
    L->next=NULL; //由于插入的新节点都会在第一个插入的节点之前，所以第一个插入的节点就是尾节点，要next指针域要初始化为null
    ElemType x;
    scanf("%d",&x);
    LNode *s;  //s是用来指向申请的新节点
    while (x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next; //新结点的next指向原本链表的第一个结点
        L->next=s;  //头节点的next指向新节点
        scanf("%d",&x);
    }
}
// 尾插法来新建链表
void list_tail_insert(LinkList &L)
{
    L= (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);
    LNode *s,*r=L;  //s是用来指向申请的新节点,r始终指向链表尾部
    while (x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        r->next=s; //尾指针的next指向新结点
        r=s;       //r要指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL;  //结束时让尾指针的next指向NULL
}
// 按位置查找
LinkList GetElem(LinkList L,int SearchPos)
{
    int i=0;  //带头结点，头节点相当于第0个结点
    if(SearchPos<0)
    {
        return NULL;
    }
    while (L&&i<SearchPos)
    {
        L=L->next;
        i++;
    }
    return L;
}
// 按值查找
LinkList LocateElem(LinkList L,ElemType SearchVal)
{
    while(L)
    {
        if(L->data==SearchVal)
        {
            return L;
        }
        L=L->next;
    }
    return NULL;
}
// 后插操作：在p结点后插入元素e
bool InsertNextNode(LNode *p,ElemType e)
{
    if(p==NULL)
        return false;
    LNode *s=(LinkList)malloc(sizeof(LNode));
    if(s==NULL) //内存不足
        return false;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}
// 前插操作：在p结点前插入元素e
bool InsertPriorNode(LNode *p,ElemType e)
{
    if(p==NULL)
        return false;
    LNode *s=(LinkList)malloc(sizeof(LNode));
    if(s==NULL) //内存不足
        return false;
    s->next=p->next;
    p->next=s;   //将新结点s连接到p之后
    s->data=p->data; //将p中元素复制到s中
    p->data=e;  //p中元素覆盖为e, 现在的s就相当于之前的p，p原来的位置是新插入的e，相当于在p之前插入e，偷天换日
    return true;
}
// 按位序插入（带头结点的），往第i个位置插入元素,i代表插入第几个位置
bool ListFrontInsert(LinkList L,int i,ElemType InsertVal)
{
    LinkList p= GetElem(L,i-1);  //查找要插入的位置的前一个元素
    //后插操作：在p结点后插入元素e
//    InsertNextNode(p,InsertVal);
    //前插操作：在p结点前插入元素e
//    InsertPriorNode(p,InsertVal);
    //按位序插入，用的后插思想
    if(NULL==p)
    {
        return false;
    }
    LinkList q;
    q=(LinkList)malloc(sizeof(LNode));  //为新结点申请空间
    q->data=InsertVal;
    q->next=p->next;
    p->next=q;
    return true;
}
// 按位序插入（不带带头结点的），往第i个位置插入元素,i代表插入第几个位置，注意&L 不带头结点的要改变头指针，加&
bool ListFrontInsertNoHeadNode(LinkList &L,int i,ElemType InsertVal)
{
    if(i<1)
        return false;
    if(i==1)  //插入第一个结点的操作和其他结点不一样
    {
        LNode *s=(LinkList)malloc(sizeof(LNode));
        s->data=InsertVal;
        s->next=L;
        L=s;
        return true;
    }
    //查找插入的i位置前一个位置
    LNode *p;
    int j=1; //当前p指针指向的第几个结点，因为没有头节点，所以刚开始指向的是第一个结点
    p=L; //p指向第一个结点（注意不是头结点）
    while (p!=NULL&&j<i-1) //循环找到第i-1个结点
    {
        p=p->next;
        p++;
    }
    //按位序插入，用的后插思想
    if(NULL==p)
    {
        return false;
    }
    LinkList q;
    q=(LinkList)malloc(sizeof(LNode));  //为新结点申请空间
    q->data=InsertVal;
    q->next=p->next;
    p->next=q;
    return true;
}
// 删除第i个位置的元素,并返回删除的元素
// 删除时L的头结点是不会变的，所以不需要加引用,返回删除的元素要加&
bool ListDelete(LinkList L,int i,ElemType &e)
{
    LinkList p= GetElem(L,i-1); //先找到要删除的元素的前一个结点
    if(p->next==NULL)
    {
        return false;
    }
    LinkList q=p->next; //拿到要删除结点的指针
    e=q->data;
    p->next=q->next;    //断链
    free(q);            //释放被删除结点空间
    return true;
}
// 删除指定结点
bool DeleteNode(LNode *p)
{
    if(p==NULL)
        return false;
    LNode *q=p->next;  //令q指向*p的后继结点
    p->data=p->next->data; //和后继结点交换数据域
    p->next=q->next; //将*q从链中断开
    free(q); //释放后继结点的存储空间
    return true;
}
void printf_list(LinkList L)
{
    L=L->next;
    while (L!=NULL)
    {
        printf("%3d",L->data);
        L=L->next;
    }
    printf("\n");
}
int main() {
    //1 2 3 4 5 9999
    LinkList L;  // L是链表头指针，是结构体指针类型
    LinkList search;
    bool ret;
    //头插法，输入数据可以为3 4 5 6 7 9999
//    list_head_insert(L);
//    printf_list(L);  //打印列表
//    printf("--------------------\n");

    //尾插法
    list_tail_insert(L);
    printf_list(L);
    printf("--------------------\n");

    // 按位置查找
    search=GetElem(L,2);
    if(search!=NULL)
    {
        printf("succeeded in searching by serial number\n");
        printf("%d\n",search->data);
    }
    printf("--------------------\n");

    // 按值查找
    search=LocateElem(L,6);
    if(search!=NULL)
    {
        printf("succeeded in searching by value\n");
        printf("%d\n",search->data);
    }
    printf("--------------------\n");

    // 往第i个位置插入元素
    ret=ListFrontInsert(L,2,99);
    if(ret)
    {
        printf("insert value successfully\n");
        printf_list(L);
    } else
    {
        printf("insert failed\n");
    }
    printf("--------------------\n");

    // 删除第i个位置的元素,并返回删除的元素
    ElemType e;
    ret=ListDelete(L,1,e);
    if(ret)
    {
        printf("delete value successfully!delete element is =%d\n",e);
        printf_list(L);
    } else
    {
        printf("delete failed\n");
    }
    printf("--------------------\n");

    return 0;
}
